package com.LeeCode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 递增顺序搜索树
 */

public class Code897 {
    public static void main(String[] args) {
        Integer[] arr = {2, 1, 4, null, null, 3};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code897().increasingBST(root).val);
    }

    public TreeNode increasingBST(TreeNode root) {
        TreeNode newRoot = null, node = root, cur = newRoot;
        Deque<TreeNode> stack = new LinkedList<>();
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            if (newRoot == null) {
                newRoot = node;
                cur = newRoot;
            } else {
                cur.left = null;
                cur.right = node;
                cur = node;
            }

            node = node.right;
        }
        cur.left = null;

        return newRoot;
    }
}
